import java.util.HashMap;
import java.util.Map;

public class Solution105 {

    public static class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;

        TreeNode() {
        }

        TreeNode(int val) {
            this.val = val;
        }

        TreeNode(int val, TreeNode left, TreeNode right) {
            this.val = val;
            this.left = left;
            this.right = right;
        }
    }

    public TreeNode buildTree(int[] preorder, int[] inorder) {
        Map<Integer,Integer> map=new HashMap<>();
        for (int i=0;i<inorder.length;i++){
            map.put(inorder[i],i);
        }
        return build(inorder,0,inorder.length-1,preorder,0,preorder.length-1,map);
    }

    private TreeNode build(int[] inorder, int s1, int e1, int[] preorder, int s2, int e2, Map<Integer, Integer> map) {
        TreeNode node=new TreeNode(preorder[s2]);
        if (s1==e1){
            return node;
        }
        int k=map.get(node.val);
        if (k>s1){
            node.left=build(inorder,s1,k-1,preorder,s2+1,k-s1+s2,map);
        }
        if (k<e1){
            node.right=build(inorder,k+1,e1,preorder,k-s1+s2+1,e2,map);
        }
        return node;
    }

    public static void main(String[] args) {
        System.out.println(new Solution105().buildTree(new int[]{3,9,20,15,7},new int[]{9,3,15,20,7}).right.right.val);
    }
}
